1. Field of the Invention
The present invention relates to an address retrieval apparatus, and more particularly to an address retrieval apparatus for retrieving a transmission destination address, to which one or more packets of data are transmitted through one or more communication networks, so as to assisting a router in distributing the one or more data packets.
All of patents, patent applications, patent publications, scientific articles and the like, which will hereinafter be cited or identified in the present application, will, hereby, be incorporated by references in their entirety in order to describe more fully the state of the art, to which the present invention pertains.
2. Description of the Related Art
A variety of communications have been realized through a variety of communication networks such as the Internet. A router is one of function units for providing interconnections between plural networks. The router retrieves a routing information which indicates or designates the transmission destination address, to which one or more data packets are transmitted. If the networks are included in the Internet, then the one or more packets may be Internet Protocol (IP) packets, so that the router decides an output port for outputting the one or more data packets. Usually, a plurality of the routers are placed over the networks. Each of the routers over the networks sequentially decides and assign the output ports for the packets for defining respective transmission routes over the networks, whereby the respective packets are transmitted through respectively assigned routes over the networks to the respective transmission destination addresses.
This routing operation made by the router is similar to a routing operation that exchanges respectively corresponding to the sequences of figures of telephone number sequentially distribute output ports for the figures of telephone number, so that a call is made upon a complete correspondence in all digits of the telephone number.
For distribution operation by each of the routers over the communication networks, the each router decides or selects one of the plural output ports based on the data included in the each packet with reference to a retrieval table included in the each router, in order to permit the each packet to be transmitted from the selected one of the plural output ports. Namely, the retrieval table enables the router to select one of the plural output ports based on the data included in the each packet.
It is possible that one or more additional terminals are added or one or more existent terminals are removed over the communication networks. It is, hereby, assumed that whereas the router selects a first output port for data packet transmission based on a route information which designates a transmission destination “A” with reference to the existent retrieval table, even any one terminal on a route between the first output port and the transmission destination “A” is removed, whereby the packet outputted from the first output port could no longer reach the transmission destination “A”. In this case, it is possible that the router may select a different output port, for example, a third output port for data packet transmission through a different roundabout route between the third output port and the transmission destination “A”. In order to respond to any change to the existent configuration of the networks, it is necessary to renew and/or change the existent retrieval table in the each router, or to register new data onto the existent retrieval table with or without deletion of the existent data.
The following descriptions will be made assuming that the data packet is the IP packet. The retrieval table in the router has a distribution information which enables the router to decide or select one of the plural output ports. The distribution information may include any next stage transfer destination, for example, an IP address of an output interface or a next stage router, to which the packet is transmitted. The distribution information may be registered as an IP Sub-Net address and a Prefix length. The term “Sub-Net” means a plurality of subordinate networks divided from the network. The “IP address” may comprise a network address and a host number, so that one or more predetermined significant bits of the host number designates a sub-net number which is used for dividing the network into the plurality of sub-networks. The term “Prefix length” means a length of an effective bit string and is represented by a bit number which corresponds to the length of the effective bit string of address.
The router selects the output port for the packet transmission with reference to the retrieval table, wherein one of the plural IP Sub-Net addresses is decided in accordance with a Longest Prefix Match method, provided that the decided one is longest, in the matched effective bit string which is identical with the IP address as a retrieval key, among the plural IP Sub-Net addresses registered on the retrieval table. It is, for example, assumed that the IP address comprises three bits, and two IP addresses “0**” and “00*” are registered on the retrieval table. The IP address “0**” has a single effective bit “0” as the first bit, while the second and third bits “*” is the arbitrary value which may be either “0” or “1”. The IP address “00*” has two effective bits “0” as the first and second bits, while the third bit “*” is the arbitrary value which may be either “0” or “1”.
The retrieval with reference to the retrieval table is made by referring the transferred IP address as the retrieval key to the two IP addresses “0**” and “00*” registered on the retrieval table, wherein the transferred IP address indicates the transmission destination, to which the packet is intended to be transmitted. If the transferred IP address is “0001. . . ”, then the bit string “00*” is longer in Prefix length than the other bit string “0**”. In this case, the Prefix-longest bit string “00*” is selected as the IP address for the next transmission destination.
If the bit number of the IP address is as small as described above, then it is easy to realize a desired high efficiency in retrieving the IP address. Unfortunately, however, the bit number of the actual and practical IP address is much longer than 3. In accordance with the Internet Protocol version 4 (IPv4), the bit number of the IP address is 32. In accordance with the recently standardized Internet Protocol version 6 (IPv6), the bit number of the IP address is 128. In such cases, it is no longer easy to realize the desired high efficiency in retrieving the IP address. Namely, it is practically difficult for the router to realize the desired high efficiency in obtaining the transmission destination information based on the data included in the each packet with reference to a retrieval table included in the each router.
There are two existent retrieval methods, for example, a Binary Tree retrieval method, and a Prefix Expansion retrieval method. The Binary Tree retrieval method utilizes a two-branched data configuration. FIG. 1 is a view illustrative of respective bit patterns of eight IP addresses P1, P2, P3, P4, P5, P6, P7 and P8. “*” represents the arbitrary value which may be either “0” or “1”. FIG. 2 is a diagram illustrative of the two-branched data configuration utilized by the Binary Tree retrieval method, wherein the eight IP addresses P1, P2, P3, P4, P5, P6, P7 and P8 constitute the two-branched tree-structure from a starting point 101. In accordance with the Binary Tree retrieval method, sequential bit referring operations from the head bit in one-bit unit or one-bit-by-one-bit are made. The two-branched tree-structure comprises a plurality of nodes including the eight IP addresses P1, P2, P3, P4, P5, P6, P7 and P8, a plurality of first type segments extending left-downwardly which correspond to “0”-bit, and a plurality of second type segments extending right-downwardly which correspond to “1”-bit, wherein each of the first and second type segments interconnects adjacent two of the plurality of nodes.
Japanese laid-open patent publication No. 11-191781 discloses an address retrieval apparatus including a hardware circuit which makes the retrieval of the address by utilizing the binary-tree structure as the routing table, wherein unnecessary branches are removed for performing a desired high speed route-retrieval operation. The use of the hardware circuit for the retrieval allows the desired high speed route-retrieval operation.
In accordance with the above retrieval method utilizing the binary-tree structure, there is any tree structure which has the same number of brunches as the maximum address bit number. In accordance with the Internet Protocol version 4, the IP address comprises 32-bits. The above example shown in FIGS. 1 and 2 is the case of 8-bits configuration. 32-bits tree-structure may have 32 brunches at the maximum. This means it necessary to make 32-times of access to the nodes. The Binary-Tree retrieval method is advantageous in view of allowing the increase in the times of access to the nodes and resulting in an undesired low efficiency of the retrieval operation. The use of the hardware for realizing the retrieval instead of any software is insufficient for compensating for the increased number of bunches of the binary-tree structure.
In order to reduce the number of bunches in the binary-tree structure, the Prefix Expansion retrieval method is effective. Japanese laid-open patent publication No. 2000-307641 discloses that the Prefix Expansion retrieval method, wherein the bit string of the IP address is divided into a plurality of divided subordinate bit strings. FIG. 3 is a diagram illustrative of a hierarchical structure of plural subordinate bit strings divided from the bit string of the IP address. The divided subordinate bit strings are configured in a hierarchical structure. First to fourth retrieval tables 111, 112, 113 and 114 are provided for the divided subordinate bit strings, respectively. In each of the first to fourth retrieval tables 111, 112, 113 and 114, the divided subordinate bit string serves as an entry address.
In the example shown in FIG. 3, there are triple-layered hierarchical structure, wherein a string of 7-bits in total of the IP address is divided into two bits for the lowest level in the triple-layered hierarchical structure, three bits for the middle level, and two bits for the highest level. The first retrieval table 111 is positioned at the highest level in the triple-layered hierarchical structure. The second and third retrieval tables 112 and 113 are positioned at the middle level in the triple-layered hierarchical structure. The fourth retrieval table 114 is positioned at the lowest level in the triple-layered hierarchical structure.
In each of the first and fourth retrieval tables 111 and 114 at the highest and lowest levels respectively, four divided subordinate bit strings “00”, “01”, “10” and “11” are the entry address. In each of the second and third retrieval tables 112 and 113 at the middle level, eight divided subordinate bit strings “000”, “001”, “010”, “011”, “100”, “101”, “110”, and “111” are the entry address.
In accordance with this Prefix Expansion retrieval method, for renewal of an IP address registered on a retrieval table, an end/continue flag which indicates whether a transmission of this IP address is ended at this retrieval table or continued to a next retrieval table, a next table pointer which indicates a next IP address for a next transfer destination are stored or registered with overlap respectively into all of the entries allowing the registrations in the entries of this retrieval table.
For registering the IP address on the each retrieval table, a bit string of an entry, which does not reach a terminal of each divided subordinate bit string, is expanded up to the terminal of each divided subordinate bit string. It is, for example, assumed that the divided subordinate bit string at one level in the hierarchical structure comprises 3-bits, while a bit string of the entry is smaller bit number, 2 bits or 1-bit. In this case, the shorter bit string is expanded to the 3-bits length. Respective short bit strings are expanded to a uniform or common bit length, so that a plurality of the bit-length-expanded entries including the short bit strings do correspond to the common registered IP address.
FIG. 4 is a view illustrative of both original IP addresses different in bit length from each and shown in FIG. 1, and expanded IP addresses up to three different bit lengths. Registered IP addresses of the eight IP addresses P1, P2, P3, P4, P5, P6, P7 and P8 are respectively expanded up to least significant bits of the respective divided subordinate bit strings. The IP address P5 has a prefix length of “1” as an effective bit string length. The IP address P5 has the original and pre-expansion bit string “0*”. The IP address P5 is expanded by one bit to 2-bits length, and has two expanded bit strings “00” and “01”. With reference back to FIG. 3, the IP address P5 is registered with overlap at both the entry addresses “00” and “01” on the first retrieval table 111 at the highest level.
The IP address P2 has a prefix length of “3” as an effective bit string length. The IP address P2 has the original and pre-expansion bit string “111*”. The IP address P2 is expanded by two bits to 5-bits length, and has four expanded bit strings “11100”, “11101”, “11110”, and “11111”. On the second and third retrieval tables 112 and 113, strings of the third to fifth significant bits correspond to the entry addresses. With reference again to FIG. 3, the IP address P2 is registered with overlap at the four entry addresses “100”, “101”, “110”, and “111” on the third retrieval table 113 at the middle level.
As described above, the bit-strings expansions of the IP addresses make the registered IP addresses correspond to specific entry addresses on the retrieval tables. This allows that the divided subordinate bit strings of the registered IP addresses are simply or directly compared to the entry addresses of the retrieval tables for the retrieval process.
Namely, the prefix expanded retrieval method limits the maximum retrieval times to the number of the multilevels of the hierarchical structure. The prefix expanded retrieval method is effective to reduce the maximum retrieval times. In the above-example shown in FIG. 3, the four retrieval tables are configured in the three-level hierarchical structure. Thus, the maximum retrieval times are only three.
Each of the first to fourth retrieval tables 111, 112, 113 and 114 further include the above-described end/continue flag, a transfer destination distribution information, a pointer effective/ineffective flag which indicates whether a pointer of the transfer destination distribution information is effective or ineffective, and a pointer to a retrieval table including a next-retrieved bit string. Those entry informations are stored or registered in all of the entries which allow the registrations thereof. For the original and pre-expansion bit string “0*”, the entry information is stored and registered in both the 1-bit-expanded strings “00” and “01”.
For registering the IP address on the each retrieval table, a bit string of an entry, which does not reach a terminal of each divided subordinate bit string, is expanded up to the terminal of each divided subordinate bit string. After the bit string has been expanded, the entry information corresponding to the original and pre-expansion bit string is entirely stored and registered on all of the retrieval tables which include the divided subordinate bit strings divided from the original and pre-expansion bit string. The write operation raises the following problems.
FIG. 5 is a view illustrative of four bit patterns of IP addresses P1, P2, P3 and P4. FIG. 6 is a view illustrative of correspondences between the expanded four-bits strings and the expanded IP addresses. With reference to FIGS. 5 and 6, an example will be described to clarify the problems in connection with the above-described prefix expanded retrieval method. It is, hereby, assumed that an original and pre-expansion bit string is longer than another original and pre-expansion bit string. The first original IP address P1 is “0” and has a single-bit length. The first original IP address P1 is expanded to 4-bits strings “0***”, for example, eighth 4-bits strings “0000”, “0001”, “0010”, “0011”, “0100”, 0101”, “0110”, and “0111”.
The second original IP address P2 is “010” and has a 3-bit length. The second original IP address P2 is expanded to 4-bits strings “010*”, for example, two 4-bits strings “0100” and “0101”.
The third original IP address P3 is “1010” and has a 4-bit length. The third original IP address P3 is not expanded.
The fourth original IP address P4 is “10” and has a 2-bit length. The fourth original IP address P4 is expanded to 4-bits strings “10**”, for example, four 4-bits strings “1000”, “1001”, “1010” and “1011”.
With reference to FIG. 6, there are theoretically sixteen different 4-bits strings which include four 4-bits strings “11**”, for example, “1100”, “1101”, “1110” and “1111” which are not derived from the four original IP addresses P1, P2, P3 and P4 shown in FIG. 5. The router is configured to respond to the expanded 4-bits strings “00**”, “01**”, and “10**”, but is not responsible to four 4-bits strings “11**”. For this reason, those four 4-bits strings “11**” are not registered (NULL) as the IP addresses, while twelve expanded 4-bits strings “00**”, “01**”, and “10**” are registered with correspondence to the four original IP addresses P1, P2, P3 and P4. For example, the bit string “0000” is registered as the first IP address P1.
It should be noted that two or more expanded IP addresses correspond to a common expanded 4-bits string, wherein the two or more expanded IP addresses conflict to each other with reference to the common expanded 4-bits string. This raises an issue of whether either one of the conflicting two or more IP addresses should be made correspond to the common expanded 4-bits string.
For example, the expanded 4-bits string “0100” is derived from the original and pre-expansion bit string “0” and corresponds to the first original IP address P1, as well as is derived from the original and pre-expansion bit string “010” and corresponds to the second original IP address P2. Namely, the first and second original IP addresses P1 and P2 conflict to each other with reference to the expanded 4-bits string “0100”. This raises an issue of whish either one of the conflicting first and second IP addresses P1 and P2 should be made correspond to the common expanded 4-bits string “0100”.
Similarly, the expanded 4-bits string “0101” is also derived from the original and pre-expansion bit string “0” and corresponds to the first original IP address P1, as well as is derived from the original and pre-expansion bit string “010” and corresponds to the second original IP address P2. Namely, the first and second original IP addresses P1 and P2 conflict to each other with reference to the expanded 4-bits string “0101”. This raises a further issue of whish either one of the conflicting first and second IP addresses P1 and P2 should be made correspond to the common expanded 4-bits string “0101”.
If two or more expanded IP addresses conflict to each other with reference to the common expanded 4-bits string, then one expanded IP address, which has a longer or longest original and pre-expansion bit string, is given a priority to correspond to the common expanded 4-bits string. Namely, an entry information corresponding to the longer original and pre-expansion bit string is registered or stored. In the above-described two examples, the original and pre-expansion bit string “010” of the second IP address P2 is longer than the original and pre-expansion bit string “0” of the first IP address P1. As shown in FIG. 6, the second IP address P2 is given the priority to correspond to the common expanded 4-bits string “0100”.
For example, the expanded 4-bits string “1010” is derived from the original and pre-expansion bit string “1010” and corresponds to the third original IP address P3, as well as is derived from the original and pre-expansion bit string “10” and corresponds to the fourth original IP address P4. Namely, the third and fourth original IP addresses P3 and P4 conflict to each other with reference to the expanded 4-bits string “1010”. This raises another issue of whish either one of the conflicting third and fourth original IP addresses P3 and P4 should be made correspond to the common expanded 4-bits string “1010”. The original and pre-expansion bit string “1010” of the third IP address P3 is longer than the original and pre-expansion bit string “10” of the fourth IP address P4. As shown in FIG. 6, the third IP address P3 is given the priority to correspond to the common expanded 4-bits string “1010”.
FIG. 7 is a diagram illustrative of one of the conventional retrieval tables. The transfer destination distribution information is referred to as “NHP”. In accordance with the conventional prefix expanded retrieval method, expanded bit strings “000”, “001”, “010”, “011”, “100”, “101”, “110”, “111”, are made corresponding to transfer destination distribution informations “NHP1”, “NHP2”, “NHP3”, “NHP4”, “NHP5”, “NHP6”, “NHP7” and “NHP8”. Further, the expanded bit strings “000”, “001”, “010”, “011”, “100”, “101”, “110”, “111”, are made corresponding to next or higher hierarchical level node pointers “LPTR1”, “LPTR2”, “LPTR3”, “LPTR4”, “LPTR5”, “LPTR6”, “LPTR7” and “LPTR8”.
FIG. 8 is a block diagram illustrative of a configuration of a conventional address retrieval apparatus for managing divided bit strings. A conventional address retrieval apparatus 120 includes a retrieval table 121, a bit string management table 122, and an IP address management process block 123 which is functionally coupled to both the retrieval table 121, and the bit string management table 122. The bit string management table 122 is essential for the conventional address retrieval apparatus 120.
FIG. 9 is a flow chart illustrative of sequential steps of a bit renewal process involved in registration, deletion and renewal processes for bit strings on the retrieval table in the conventional address retrieval apparatus shown in FIG. 8. In the step S201, registration, deletion or renewal is made of a subject bit string on the bit string management table 122. In the step S202, an original and pre-expansion bit string is obtained from the bit string management table 122. In the step S203, the original and pre-expansion bit string is expanded to a longer bit string of a predetermined bit number. In the step S204, a calculation is made of the bit string to be stored into the retrieval table 121. During the calculation, if the same bit strings are present, then one of the bit strings is selected, wherein the selected one is derived from the original and pre-expansion bit string which is longer than the original and pre-expansion bit string which was expanded to the unselected one. In the step S205, the calculated bit strings are stored on the retrieval table 121. The renewal process is then completed.
The conventional address retrieval apparatus 120 needs not only the retrieval table 121 but also the bit string management table 122. For taking place at least one of the registration, deletion and renewal processes, it is necessary to expand the divided bit string to the predetermined bit number.
In accordance with the prefix expanded retrieval method, as described above, an entry information storing regulation is necessary, for which reason it is impossible to leave pre-expansion informations on the retrieval table, where the pre-expansion information indicates a configuration of the original and pre-expansion bit string. For this reason, the original and pre-expansion bit string configuration information is necessary for taking place at least one of the registration, deletion and renewal processes. In order to hold the original and pre-expansion bit string configuration information, an additional table for managing he retrieval table is further needed.
With reference again to FIG. 5, descriptions will be made, assuming that the IP address P2 is deleted. In this example, two bit strings “0100” and “0101” are deleted. The retrieval table does not include any effective information of what should be stored at positions of the two bit strings “0100” and “0101”. For example, two different-length bit configurations “A” and “B” are present, wherein the bit configuration “A” is longer than the bit configuration “B”. The longer bit configuration “A” is registered on the retrieval table. Any change is caused of the communication network, whereby a router becomes not needing the longer bit configuration “A”. Thus, the bit configuration “A” and its accompanying transfer destination distribution information should be deleted from the retrieval table. Notwithstanding, the retrieval table does not include any effective or useful information which indicates which bit configuration would conflict with the bit configuration “A”, namely, the retrieval table does not include any effective or useful information which indicates which bit string should be registered instead of deletion of the bit configuration “A”.
For the prefix expanded retrieval method, it is necessary to store, on the retrieval table, the same number of the transfer destination distribution informations as the registered bit strings. Further, it is necessary that each hierarchical level or layer for retrieval of the divided bit strings holds those transfer destination distribution informations. The conventional address retrieval apparatus performing the prefix expanded retrieval method needs a relatively large memory size for managing the retrieval table.
In the above circumstances, the development of a novel address retrieval apparatus free from the above problems is desirable.